#leetcode题目57：插入区间
#难度：中等
#时间复杂度：O(n)
#空间复杂度：O(1)
#方法：双指针

from typing import List
class Solution:
    #方法一：ai解法
    # def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    #     intervals.append(newInterval)
    #     intervals.sort()
    #     res=[intervals[0]]
    #     for x,y in intervals[1:]:
    #         if x>res[-1][1]:
    #             res.append([x,y])
    #         else:
    #             y=max(res[-1][1],y)
    #             res[-1][1]=y
    #     return res

    #方法二：视频解法
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        if not intervals:
            return [newInterval]
        if newInterval[0]>intervals[-1][1]:
            return intervals+[newInterval]
        if newInterval[1]<intervals[0][0]:
            return [newInterval]+intervals
        
        
        i,n=0,len(intervals)
        while i<n and newInterval[0]>=intervals[i][1]:
            i+=1

        if intervals[i][0]>newInterval[1]:
            return intervals[:i]+[newInterval]+intervals[i:]

        tmp=i
        left=min(newInterval[0],intervals[i][0])
        right=newInterval[1]
        while i<n and newInterval[1]>=intervals[i][0]:
            right=max(right,intervals[i][1])
            i+=1
        return intervals[:tmp]+[[left,right]]+intervals[i:]



#测试数据
intervals=[[1,3],[6,9]]
newInterval=[2,5]
#预期输出：[[1,5],[6,9]]
solution=Solution()
print(solution.insert(intervals,newInterval))

intervals=[[1,2],[3,5],[6,7],[8,10],[12,16]]
newInterval=[4,8]
#预期输出：[[1,2],[3,10],[12,16]]
solution=Solution()
print(solution.insert(intervals,newInterval))

intervals=[]
newInterval=[5,7]
#预期输出：[[5,7]]
solution=Solution()
print(solution.insert(intervals,newInterval))

intervals=[[1,5]]
newInterval=[2,3]
#预期输出：[[1,5]]
solution=Solution()
print(solution.insert(intervals,newInterval))

intervals=[[1,5]]
newInterval=[2,7]
#预期输出：[[1,7]]
solution=Solution()
print(solution.insert(intervals,newInterval))

